package main.java.LeetCode.SolutionVersionOne;


import main.java.LeetCode.CommonSolution.ListNode;
import main.java.LeetCode.CommonSolution.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

@SuppressWarnings("all")
public class Solution {
    public int[] twoSum(int[] nums,int target){
        int [] result = new int[2];
//        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        for(int i:list) {
            if(list.contains(target-i)&&i!=(target-i)){
                result[1] = list.indexOf(i);
                result[0] = list.indexOf(target-i);
                break;
            }
            if(list.contains(target-i)&&i==(target-i)&&list.subList(list.indexOf(i)+1, list.size()).contains(i)){
                result[1] = list.indexOf(i);
                result[0] = list.subList(list.indexOf(i)+1, list.size()).indexOf(i)+result[1]+1;
                return result;
            }
        }
        HashMap<Object, Object> map = new HashMap<>();

        return result;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode headNode = null;
        int temp=0;
        while(true) {

            if (l1.val + l2.val + temp > 9) {

                if (head == null) {
                    head = new ListNode(l1.val + l2.val - 10 + temp);
                    headNode = head;
                } else {
                    head.next = new ListNode(l1.val + l2.val - 10 + temp);
                    head = head.next;
                }
                temp = 1;

            } else {

                if (head == null) {
                    head = new ListNode(l1.val + l2.val + temp);
                    headNode = head;
                } else {
                    head.next = new ListNode(l1.val + l2.val + temp);
                    head = head.next;
                }
                temp = 0;
            }
            l2 = l2.next;
            l1 = l1.next;
            if(l1==null||l2==null)
                break;
        }

        if(l2==null&&l1!=null){
            if(temp==0){
                while(l1!=null){
                    head.next = l1;
                    head = head.next;
                    l1 = l1.next;
                }
            }else{
                while (l1 != null){
                    int val = l1.val+temp;
                    if(val>9){
                        head.next = new ListNode(val-10);
                        temp = 1;
                    }else{
                        head.next = new ListNode(val);
                        temp = 0;
                    }
                    head = head.next;
                    l1 = l1.next;
                }
            }
        }else{
            if(l2!=null&&l1==null){
                if(temp==0){
                    while(l2!=null){
                        head.next = l2;
                        head = head.next;
                        l2 = l2.next;
                    }
                }else{
                    while (l2 != null){
                        int val = l2.val+temp;
                        if(val>9){
                            head.next = new ListNode(val-10);
                            temp = 1;
                        }else{
                            head.next = new ListNode(val);
                            temp = 0;
                        }
                        head = head.next;
                        l2 = l2.next;
                    }
                }
            }
        }

        if(temp==1)
            head.next = new ListNode(1);
        return headNode;


    }

    public ListNode arrayToList(int[] arrays){
        ListNode head = null;
        ListNode headNode = null;
        for(int i:arrays){
            if(head==null){
                head = new ListNode(i);
                headNode = head;
            }
            else{
                 head.next = new ListNode(i);
                 head = head.next;
            }
        }
        return headNode;
    }

    public int lengthOfLongestSubstring(String s) {
        int maxLength = 1;
        int strLength = s.length();
        if(strLength==0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0),0);
        for(int i=1;i<strLength;i++){
                if(!map.containsKey(s.charAt(i))){
                    map.put(s.charAt(i),i);
                    if(maxLength<map.size())
                        maxLength=map.size();
                }else{
                    int j = map.get(s.charAt(i));
                    map.clear();
                    for(int c =j+1;c<=i;c++){
                            map.put(s.charAt(c),c);
                    }
                    if(maxLength<map.size())
                        maxLength=map.size();

                }

        }

        return maxLength;

    }

    public int reverse(int x){
        boolean isN = false;
        if(x<0){
            x = -x;
            isN = true;
        }
        String s ="";
        int modNum=0;
        int sum = 0;
        while(x!=0){
            modNum = x%10;
            x = (int)(x /10-modNum/10);
//            System.out.println(modNum+"->");
            if(modNum==0&&s.length()>0){
                s =s+modNum;
            }
            if(modNum!=0){
                s=s+modNum;
            }

        }
        try{
            sum= Integer.parseInt(s);
        }catch(Exception e){
            return 0;
        }

        if(isN)
            sum = -sum;

        return sum;
    }

    public double findMedianSortedArrays(int[] nums1,int [] nums2){
        int l1 = nums1.length;
        int l2 = nums2.length;
        int flag;
        int p1 = 0;
        int p2 = 0;

        if(l1==0){
            if((l1+l2)%2==1){
                return nums2[l2/2];
            }else{
                return (double)(nums2[l2/2]+nums2[l2/2-1])/2;
            }
        }
        if(l2==0){
            if((l1+l2)%2==1){
                return nums1[l1/2];
            }else{
                return (double) (nums1[l1/2]+nums1[l1/2-1])/2;
            }
        }

        if((l1+l2)%2==1){
            flag=(l1+l2)/2+1;
            while (true){
                if(nums1[p1]<nums2[p2]){
                    if(p1+p2+1==flag){
                        return nums1[p1];
                    }
                    p1++;
                    if(p1==l1){
                        System.out.println("p1到头了");
                        while (true){
                            if(p1+p2==flag){
                                System.out.println(p2);
                                return nums2[p2-1];
                            }
                            p2++;
                        }
                    }
                }else{
                    if(p1+p2+1==flag){
                        return nums2[p2];
                    }
                    p2++;
                    if(p2==l2){
                        while (true){
                            if(p1+p2==flag)
                                return nums1[p1-1];
                            p1++;
                        }
                    }
                }
            }
        }else{
            double sum = 0;
            flag=(l1+l2)/2+1;
            int breakPoint = 0;
            while (true){
                if(nums1[p1]<nums2[p2]){
                    if(p1+p2+1==flag-1||p1+p2+1==flag){
                        sum = sum+nums1[p1];
                        breakPoint++;
                        if(breakPoint==2)
                            return sum/2;
                    }
                    p1++;
                    if(p1==l1){
                        while (true){
                            if(p1+p2+1==flag-1||p2+p1+1==flag){
                                sum = sum+nums2[p2];
                                breakPoint++;
                                if(breakPoint==2)
                                    return sum/2;
                            }

                            p2++;
                        }
                    }
                }else{
                    if(p1+p2+1==flag-1||p1+p2+1==flag){
                        sum = sum+nums2[p2];
                        breakPoint++;
                        if(breakPoint==2)
                            return sum/2;
                    }
                    p2++;
                    if(p2==l2){
                        while (true){
                            if(p1+p2+1==flag-1||p2+p1+1==flag){
                                sum = sum+nums1[p1];
                                breakPoint++;
                                if(breakPoint==2)
                                    return sum/2;
                            }

                            p1++;
                        }
                    }
                }
            }
        }

    }

    public double findMedianSortedArraysOffice(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }


    }

    public int myAtoi(String s){
//        s = s.split();
        int result = 0;
        int strLength = s.length();
        if(strLength==0)
            return 0;
        boolean flag = false;

        for(int i=0;i<strLength;i++){
            if(i==0&&s.charAt(i)=='-'){
                flag = true;
                continue;
            }
            if(i==0&&s.charAt(i)=='+')
                continue;

            if(!Character.isDigit(s.charAt(i))){
                s = s.substring(0,i);
                break;
            }
        }
        System.out.println(s);
        if(s==""||s.equals("-")||s.equals("+"))
            return 0;
        try {
                result = Integer.parseInt(s);
        }catch (Exception e){
            if(!flag)
                return Integer.MAX_VALUE;
            else
                return Integer.MIN_VALUE;
        }
        return result;


    }

    public int maxArea(int[] height) {

        return 0;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list =new ArrayList<>();
        HashSet<List<Integer>> hashSet = new HashSet<>();
        int Length = nums.length;

        Arrays.sort(nums);
        if(nums[0]+nums[1]+nums[2]>0||nums[Length-1]+nums[Length-2]+nums[Length-3]<0)
            return list;

        int p1=0,p2=1,p3=Length-1;
        boolean isP2Change = false;

        while(true){
            if(p3-p1==2){
                if(nums[p1]+nums[p2]+nums[p3]==0){
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[p1]);
                    arrayList.add(nums[p2]);
                    arrayList.add(nums[p3]);
                    hashSet.add(arrayList);
                }
                break;
            }

            if(p3<=p2){
                p1++;
                p2=p1+1;
                p3=Length-1;

            }

            for(int i=p3;i>p2;i--){
                if(nums[p1]+nums[p2]+nums[i]<0){
                    isP2Change = true;
                    p2++;
                    break;
                }
                if(nums[p1]+nums[p2]+nums[i]==0){
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[p1]);
                    arrayList.add(nums[p2]);
                    arrayList.add(nums[i]);
                    hashSet.add(arrayList);
                    p2++;
                    p3=i;
                    isP2Change = true;
                    break;
                }
            }
            if(!isP2Change){
                p2++;
            }else
                isP2Change = false;

        }

        return hashSet.stream().collect(Collectors.toList());
    }

    public List<List<Integer>> threeSumBetter(int[] nums){
        HashSet<List<Integer>> list = new HashSet<>();
        int Length = nums.length;
        Arrays.sort(nums);
        if(nums[0]+nums[1]+nums[2]>0||nums[Length-1]+nums[Length-2]+nums[Length-3]<0)
            return list.stream().collect(Collectors.toList());
        int p1,p2,p3,temp=-1;
        for(p1=0;p1<Length-2;p1++){
            if(p1>0&&nums[p1]==nums[p1-1])
                break;
            p2 = p1+1;
            p3 = Length -1;
            while (p2<p3){
                temp = nums[p1]+nums[p2]+nums[p3];
                if(temp<0)
                    p2++;
                else if(temp>0)
                    p3--;
                else {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[p1]);
                    arrayList.add(nums[p2]);
                    arrayList.add(nums[p3]);
                    list.add(arrayList);
                    p2++;
                    p3--;
                }
            }
        }
        return list.stream().collect(Collectors.toList());

    }

    public List<String> letterCombinations(String digits) {
        String temp = "";
        ArrayList<String> list = new ArrayList<>();
        ArrayList<String> stringArrayList = new ArrayList<>();
        if(digits.length()==0)
            return list;
        for(int i=0;i<digits.length();i++){
            char tempChar = digits.charAt(i);
            if(tempChar<'7'){
                int tempInteger = (int)tempChar;
                tempInteger = (tempInteger-50)*2+tempInteger+47;
                temp=temp+String.valueOf((char)(tempInteger))+String.valueOf((char)(tempInteger+1))+String.valueOf((char)(tempInteger+2));
            }else if(tempChar=='7'){
                temp=temp+"pqrs";
            }else if(tempChar=='8'){
                temp = temp+"tuv";
            }else
                temp = temp+"wxyz";
            stringArrayList.add(temp);
            temp="";

        }

        return findList(list,stringArrayList,0,temp);

    }
    public List<String> findList(List list,List<String> stringList,int flag,String subString){

        String s= stringList.get(flag);
        for(int i=0;i<s.length();i++){
            if(flag==stringList.size()-1){
                list.add(subString+s.charAt(i));
            }
            else {
                subString = subString+s.charAt(i);
                flag = flag+1;
                list = findList(list,stringList,flag,subString);

                subString = subString.replaceFirst(".$","");
                flag--;
            }
        }
        return list;
    }

    public ListNode removeNthFromEnd(ListNode head,int n){
        ListNode tempHead = head;
        ListNode Tail = head;
        ListNode preHead = null;
        if(head.next==null&&n>=1)
            return null;
        while (n>1){
            Tail = Tail.next;
//            System.out.println(Tail.val);
            n--;
        }
        while (Tail.next!=null){
            preHead = tempHead;
            tempHead = tempHead.next;
            Tail = Tail.next;
        }
        if(preHead==null)
            head =head.next;
        else
            preHead.next = tempHead.next;
        return head;
    }

    public ListNode swapPairs(ListNode head) {
        ListNode tempHead = head;
        if(head ==null){
            return null;
        }
        ListNode next = head.next;
        int tempVal;
        while (next!=null){
            tempVal = tempHead.val;
            tempHead.val = next.val;
            next.val = tempVal;
            tempHead = next.next;
            if(tempHead==null)
                break;
            next = tempHead.next;
        }
        return head;
    }

    public boolean isValid(String s) {

        int strLength = s.length();
        if(strLength%2!=0)
            return false;
        boolean [] isMatch = new boolean[strLength];
        boolean Match = false;
        for(int i= 0;i<strLength;i++){


            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){

                for(int j = i;j<strLength;j++){

                    if((int)s.charAt(j)-1==(int)s.charAt(i)||(int)s.charAt(j)-2==(int)s.charAt(i)&&!isMatch[j]){
                        isMatch[j]=true;
                        Match = true;
                        break;
                    }
                }

            }


            else{
                if(!isMatch[i]){
                    return false;
                }

                else
                    Match = true;

            }
            if(!Match)
                return false;
            else
                Match = false;
        }
        return true;
    }

    public boolean isValidCurrent(String s){
        int strLength = s.length();
        if(strLength%2!=0)
            return false;
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i<strLength;i++){
            if(stack.isEmpty())
                stack.add(s.charAt(i));
            else{
                if((int)stack.peek()==(int)s.charAt(i)-1||(int)stack.peek()==(int)s.charAt(i)-2)
                    stack.pop();
                else
                    stack.add(s.charAt(i));
            }
        }
        if(!stack.isEmpty())
            return false;
        return true;
    }

    public List<String> generateParenthesis(int n){
        ArrayList<String> resList = new ArrayList<>();
        StringBuilder builder = new StringBuilder();
        builder.append('(');
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('(',1);
        map.put(')',0);

        findParenthesis(map,resList,n,builder);

        return resList;
    }
    public void findParenthesis(HashMap<Character,Integer> map,List<String> list,int n,StringBuilder resStr){
        if(map.get(')')==n){
            list.add(resStr.toString());
            return;
        }

        String s = "()";
        for(int i=0;i<2;i++){
            Character tempChar = s.charAt(i);
            if(tempChar=='('&&map.get(tempChar)==n)
                continue;
            if(map.get('(')>map.get(')')){
                map.replace(tempChar,map.get(tempChar)+1);
                resStr.append(tempChar);
                findParenthesis(map,list,n,resStr);
                resStr.deleteCharAt(resStr.length()-1);
                map.replace(tempChar,map.get(tempChar)-1);
            }
            if(map.get('(')==map.get(')')&&tempChar=='('){
                map.replace(tempChar,map.get(tempChar)+1);
                resStr.append(tempChar);
                findParenthesis(map,list,n,resStr);
                resStr.deleteCharAt(resStr.length()-1);
                map.replace(tempChar,map.get(tempChar)-1);
            }
        }
    }

    public int removeDuplicates(int[] nums){
        HashSet<Integer> set = new LinkedHashSet<>();
        int j=0;
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        for(Integer i:set){
            nums[j]=i;
            j++;
        }
        return set.size();
    }

    public int strStr(String haystack,String needle){
        int StrLength = haystack.length();
        int strLength = needle.length();
        int matchChar = needle.charAt(0);
        int res = -1;
        for(int i=0;i<StrLength-strLength;i++){
            if(haystack.charAt(i)==matchChar&&haystack.substring(i,i+strLength).equals(needle)){
                res = i;
                break;
            }
        }
        return res;
    }

    public List<Integer> findSubstring(String s,String[] words){
        int subStrLength = words[0].length();
        int strLength = s.length();
        LinkedList<Integer> list = new LinkedList<>();
        if(subStrLength*words.length>strLength)
            return list;
        HashMap<String,Integer> temp = new HashMap<>();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i=0;i< words.length;i++)
            map.put(words[i],map.getOrDefault(words[i],0)+1);

        int left = 0;
        int rightLength = words.length*subStrLength;

        while (left+subStrLength* words.length<=strLength){

            StringBuffer stringBuffer =new StringBuffer(s.substring(left,left+rightLength));
            System.out.println(stringBuffer);
            for(int j = 0;j<stringBuffer.length();j+=subStrLength){
                String subStr = stringBuffer.substring(j,j+subStrLength);
                if(map.containsKey(subStr)){
                    temp.put(subStr,temp.getOrDefault(subStr,0)+1);
                    if(temp.get(subStr)>map.get(subStr)){
                        temp.clear();
                        break;
                    }
                }
                else{
                    temp.clear();
                    break;
                }

            }
            if(!temp.isEmpty()){
                list.add(left);
                temp.clear();
            }
             left = left+1;
        }
        return list;
    }

    public void nextPermutation(int[] nums){
        int temp = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = nums.length - 1;i>=0;i--){
            for (int j = nums.length-1;j>i;j--){
                if(nums[j]>nums[i]){
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    for(int k = i+1;k<nums.length;k++){
                        list.add(nums[k]);
                    }
                    Collections.sort(list);
                    int val = i+1;
                    for(int n:list){
                        nums[val] = n;
                        val++;
                    }
                    return;
                }
            }
        }
        int left = 0;
        int right = nums.length-1;
        while (left<right){
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    public int findPointInArrays(int[] nums,int target){
        int arraysLength = nums.length;
        if(arraysLength==0)
            return -1;
        if(arraysLength ==1){
            if(nums[0]==target)
                return 0;
            else
                return -1;
        }
        int left = 0;
        int right = arraysLength-1;
        int mid  = 0;
        while (left<=right){
            if(nums[left]==target)
                return left;
            if(nums[right]==target)
                return right;

            if(left==right-1&&nums[right]!=target&&nums[left]!=target)
                return -1;

            mid = (left+right)/2;
            if(nums[mid]<target)
                left = mid;
            else if(nums[mid]>target)
                right = mid;
            else
                return mid;
        }
        return -1;
    }

    public int[] searchRange(int[] nums,int target){
        int[] res = new int[2];
        int p = findPointInArrays(nums,target);
        int start = p;
        int end = p;
        boolean startFlag = false;
        boolean endFlag = false;
        if(p == -1){
            res[0]=-1;
            res[1]=-1;
            return res;
        }
        else {
            while (true){
                if(start-1>=0&&nums[start-1]==nums[start])
                    start = start-1;
                else startFlag=true;

                if((end+1)< nums.length&&nums[end+1]==nums[end]){
                    end = end+1;
                }
                else endFlag=true;
                if(startFlag&&endFlag)
                    break;
            }
            res[0] = start;
            res[1] = end;
        }
        return res;
    }

    public List<List<Integer>> combinationSum(int[] candidates,int target){
        Arrays.sort(candidates);
        int Length = candidates.length;
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        LinkedList<Integer> tempList = new LinkedList<>();
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        LinkedList<List<Integer>> lists = new LinkedList<>();
        findSumEqualTarget(candidates,target,0,deque,lists,0);
        return set.stream().collect(Collectors.toList());
    }
    public void findSumEqualTarget(int []nums,int target,int begin,Deque<Integer> tempList,LinkedList<List<Integer>> lists,int sum){
        int length = nums.length;
        for(int i = begin;i<length;i++){

            if(sum+nums[i]==target){
                tempList.add(nums[i]);
                System.out.println(tempList);
                List resList = new LinkedList<>(tempList);
                lists.add(resList);
                tempList.removeLast();
                return;
            }
            if(sum+nums[i]>target)
                return;

            if(sum+nums[i]<target){
                tempList.addLast(nums[i]);
                sum = sum+nums[i];
                findSumEqualTarget(nums,target,i,tempList,lists,sum);
                sum = sum-nums[i];
                tempList.removeLast();
            }
        }
    }

    public int longestValidParentheses(String s){
        int strLength = s.length();
        if(strLength==0)
            return 0;
        int res = 0;
        ArrayDeque<Integer> PointDeque = new ArrayDeque<>();
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for(int i=0;i<strLength;i++){

            if(deque.isEmpty()){
                deque.push(s.charAt(i));
                PointDeque.push(i);
                continue;
            }

            if(s.charAt(i)==')'){
                if(deque.peek()=='('){
                    deque.pop();
                    PointDeque.pop();
                }
                else {
                    deque.push(s.charAt(i));
                    PointDeque.push(i);
                }
            }
            else{
                deque.push(s.charAt(i));
                PointDeque.push(i);
            }
        }
        int temp = strLength-1;
        int tempMAX = 0;


        if(PointDeque.isEmpty())
            return strLength;
        else{
            PointDeque.addLast(0);
            for(Integer num:PointDeque){
                tempMAX = temp - num;
                if(tempMAX%2!=0)
                    tempMAX = tempMAX-1;
                if(tempMAX>res)
                    res = tempMAX;
                temp = num;
            }
        }
//        System.out.println(PointDeque);

        return res;

    }

    public List<List<Integer>> permute(int[] nums){
        int strLength = nums.length;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        LinkedList<List<Integer>> linkedList = new LinkedList<>();
        boolean[] isRoute = new boolean[strLength];
        if(strLength==1){
            deque.addLast(nums[0]);
            linkedList.add(deque.stream().collect(Collectors.toList()));
            return linkedList;
        }
        Arrays.sort(nums);
        findPermute(nums,deque,linkedList,isRoute);

        return linkedList;
    }
    public void findPermute(int [] nums,ArrayDeque<Integer> deque,List<List<Integer>> lists,boolean[] isRoute){
        if(deque.size()==nums.length){
            List<Integer> tempList = new LinkedList<>(deque);
            lists.add(tempList);
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(isRoute[i]||(i>0&&nums[i]==nums[i-1]&&!isRoute[i-1]))
                continue;

            if(!isRoute[i])
            {
                deque.addLast(nums[i]);
                isRoute[i] = true;
                findPermute(nums,deque,lists,isRoute);
                deque.removeLast();
                isRoute[i] = false;
            }
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates,int target){
        int length = candidates.length;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        List<List<Integer>> lists = new LinkedList<>();
        boolean[] isRoute = new boolean[length];
        Arrays.sort(candidates);
        findCombinationSum2(candidates,target,deque,lists,isRoute,0);
        return lists;
    }
    public void findCombinationSum2(int [] nums,int target,ArrayDeque<Integer> deque,List<List<Integer>> lists,boolean[] isRoute,int begin){
        if(target<0){
            return;
        }
        if(target==0){
            List<Integer> list = new LinkedList<>(deque);
            lists.add(list);
            return;
        }
        for(int i = begin;i<nums.length;i++){
            if(isRoute[i]||(i>0&&nums[i]==nums[i-1]&&!isRoute[i-1]))
                continue;
            if(!isRoute[i]){
                deque.addLast(nums[i]);
                target = target-nums[i];
                isRoute[i] = true;
                findCombinationSum2(nums,target,deque,lists,isRoute,i);
                deque.removeLast();
                target = target+nums[i];
                isRoute[i] = false;
            }
        }
    }

    public int firstMissingPositive(int [] nums){
        int strLength = nums.length;
        int ans=strLength;
        boolean flag = false;
        for(int i = 0;i<strLength;i++){
            if(nums[i]<=0){
                nums[i]=strLength+1;
            }
        }
        for(int i = 0;i<strLength;i++){
            if(nums[i]<=strLength&&nums[i]>0&&nums[nums[i]-1]>0){
                nums[nums[i]-1] = -nums[nums[i]-1];
            }

            if(nums[i]<0&&-nums[i]<=strLength&&nums[-nums[i]-1]>0){
                int temp = -nums[i];
                nums[temp-1] = -nums[temp-1];
            }
        }
        for(int i=0;i<strLength;i++){
            if(nums[i]>0){
                ans = i+1;
                flag =true;
                break;
            }
        }
        if(flag)
            return ans;
        else return ans+1;

    }

    public List<List<String>> groupAnagrams(String[] strs){
        Map<String,List<String>> stringListMap = new HashMap<>();
        for(String str:strs){
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = stringListMap.getOrDefault(key, new ArrayList<>());
            list.add(str);
            stringListMap.put(key,list);
        }
        return new ArrayList<List<String>>(stringListMap.values());
    }

    public String countAndSay(int n){
        if(n==1)
            return "1";
        if(n==2)
            return "11";
        int count=0;
        String s = "11";
        StringBuilder builder = new StringBuilder();
        char temp = 0;
        for(int i=2;i<n;i++)
        {
            int start = 0;
            int end = start;
            while (end<s.length())
            {
                if(s.charAt(start)==s.charAt(end))
                {
                    end++;
                    count++;
                }
                else
                {
                    builder.append(count+""+s.charAt(start));
                    start = end;
                    count = 0;
                }
            }
            builder.append(count+""+s.charAt(start));
            s = builder.toString();
            System.out.println(s);
            count = 0;
            builder.delete(0,builder.length());
        }
        return s;
    }

    public List<List<Integer>> fourSum(int[] nums,int target){
        LinkedList<List<Integer>> lists = new LinkedList<>();
        int length = nums.length;
        if(length<4)
            return lists;
        Arrays.sort(nums);
        if((long)nums[length-1]+nums[length-2]+nums[length-3]+nums[length-4]<target)
            return lists;
        if((long)nums[0]+nums[1]+nums[2]+nums[3]>target)
            return lists;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        boolean [] isRoute= new boolean[length];
        fourSumIsTarget(nums,target,deque,lists,isRoute,-1);
        return lists;

    }
    private void fourSumIsTarget(int[] nums,int target,ArrayDeque<Integer> deque,List<List<Integer>> lists,boolean[] isRoute,int begin){
        if(deque.size()==4){
            if(target==0)
                lists.add(new ArrayList<>(deque));
            return;
        }

        for(int i=begin+1;i<nums.length;i++)
        {
            if(isRoute[i]||i>0&&nums[i]==nums[i-1]&&!isRoute[i-1])
                continue;
            if(!isRoute[i]){
                deque.addLast(nums[i]);
                target = target - nums[i];
                isRoute[i] = true;
                if(target<0&&i<nums.length-1&&nums[i+1]>0)
                {
                    target = target+nums[i];
                    isRoute[i] = false;
                    deque.removeLast();
                    return;
                }
                fourSumIsTarget(nums, target, deque, lists, isRoute, i);
                target = target+nums[i];
                isRoute[i] = false;
                deque.removeLast();
            }
        }
    }

    public int threeSumClosest(int[] nums,int target){
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        int res = 0;
        boolean isFind = false;
        Arrays.sort(nums);
        for(int i =0;i<nums.length-1;i++){
            int start = i+1;
            int end = nums.length-1;
            while (end>start)
            {
                sum = nums[i]+nums[end]+nums[start];
                System.out.println(sum);
                if(ans>Math.abs((sum-target)))
                {
                    res = sum;
                    ans = Math.abs((sum - target));
                }
                if(sum>target)
                    end--;
                if(sum<target)
                    start++;
                if(sum==target){
                    isFind = true;
                    break;
                }
            }
            if(isFind)
                break;
        }
        return res;
    }

    public double myPow(double x,int n){
        long N = n;
        return N>0?quickMul(x,N):1.0/quickMul(x,-N);

    }
    private double quickMul(double x,long n){
        if(n==0)
            return 1;
        if(n==1)
            return x;
        double temp = 1;
        if(n%2==0)
        {
            temp = quickMul(x,n/2);
            return temp*temp;
        }
        if(n%2==1)
        {
            return quickMul(x,n-1)*x;
        }
        return 0;
    }

    public int searchInsert(int[] nums,int target){
        int start = 0;
        int end = nums.length-1;
        int mid = 0;
        while (start<=end){
            if(start==end&&nums[start]!=target)
                break;
            mid = (start+end)/2;
            if(nums[mid]>target)
            {
                end = mid-1;
            } else if (nums[mid]<target) {
                start = mid+1;
            }
            else
                return mid;
        }
        if(nums[start]<target)
            return start+1;
        if(nums[start]>target)
            return start;

        return 0;

    }

    public ListNode mergeTwoLists(ListNode list1,ListNode list2){
        ListNode head = new ListNode(-1);
        ListNode tempHead = head;

        while (list1!=null&&list2!=null)
        {
            if(list1.val<list2.val)
            {
                tempHead.next = list1;
                list1 = list1.next;
            }
            else {
                tempHead.next = list2;
                list2 = list2.next;
            }
            tempHead = tempHead.next;

        }

        ListNode node = list1==null?list2:list1;
        tempHead.next = node;

        return head.next;
    }

    public int removeElement(int[] nums,int val){
        int length = nums.length;
        if(length==0)
            return 0;

        int right = 0;
        int left = length-1;

        while (right<left){
            if(right == left)
                break;
            if(nums[right]==val)
            {
                if(nums[left]!=val)
                {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                right++;
                }
                left--;
            }
            else
                right++;
        }

        return nums[right]==val?right:right+1;
    }

    public String longestCommonPrefix(String[] strs){

        int length = strs.length;
        if(length==0)
            return "";
        StringBuilder builder = new StringBuilder();
        for(int i = 0;i<length;i++)
        {
            if(i==0)
            {
                builder.append(strs[i]);
                continue;
            }

            int flag = 0;
            while (builder.substring(0,flag).equals(strs[i].substring(0,flag)))
            {
                flag++;
                if(flag>builder.length()||flag>strs[i].length())
                {
                    break;
                }
            }
            if(flag==1)
            {
                return "";
            }
            builder = new StringBuilder(builder.substring(0,flag-1));
            System.out.println(builder);

        }
        return builder.toString();
    }

    public int romanToInt(String s){
        int length = s.length();
        if(length==0)
            return 0;


        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);

        int sum = 0;
        for(int i = length-1;i>=0;i--)
        {
            char tempChar = s.charAt(i);
            if((tempChar=='V'||tempChar=='X')&&i>0&&s.charAt(i-1)=='I')
            {
                sum = sum+map.get(tempChar)-map.get('I');
                i = i-1;
                continue;
            }
            if((tempChar=='L'||tempChar=='C')&&i>0&&s.charAt(i-1)=='X')
            {
                sum = sum+map.get(tempChar)-map.get('X');
                i = i-1;
                continue;
            }
            if((tempChar=='D'||tempChar=='M')&&i>0&&s.charAt(i-1)=='C')
            {
                sum = sum+map.get(tempChar)-map.get('C');
                i = i-1;
                continue;
            }

            sum = sum+map.get(tempChar);
        }
        return sum;
    }

    public String intToRoman(int num){
        if(num==0)
            return "";

        HashMap<Integer, String> map = new HashMap<>();
        map.put(1,"I");
        map.put(4,"IV");
        map.put(5,"V");
        map.put(9,"IX");
        map.put(10,"X");
        map.put(40,"XL");
        map.put(50,"L");
        map.put(90,"XC");
        map.put(100,"C");
        map.put(400,"CD");
        map.put(500,"D");
        map.put(900,"CM");
        map.put(1000,"M");

        int[] nums = new int[map.size()];
        int n = 0;
        StringBuilder builder = new StringBuilder();
        for(int i:map.keySet())
        {
            nums[n] = i;
            n++;
        }
        Arrays.sort(nums);
        n = n-1;

        while (num>0){
            if(num>=nums[n])
            {
                num = num-nums[n];
                builder.append(map.get(nums[n]));
            }
            else
            {
                n--;
            }
        }

        return builder.toString();
    }

    public String convert(String s,int numRows){
        if(numRows==1)
            return s;
        int length = s.length();
        if(length==0)
            return "";
        int cloumn = (length-numRows)%(numRows-1)>0?(length-numRows)/(numRows-1)+2:(length-numRows)/(numRows-1)+1;
        Character[][] characters = new Character[numRows][cloumn];
        int r=0;
        int index = 0;
        for(int c = 0;c<cloumn;c++){

            if(c%2==0)
            {
                if(c==0)
                     r = 0;
                else
                    r = 1;
                while (r<numRows&&index<length)
                {
                    characters[r][c] = s.charAt(index);
                    index = index+1;
                    r =r+1;
                }
            }
            else
            {
                r = numRows-2;
                while (r>=0&&index<length)
                {
                    characters[r][c] = s.charAt(index);
                    index = index+1;
                    r = r-1;
                }
            }



        }
        String ans = "";

        for(int i = 0;i<numRows;i++){
            for (int j = 0;j<cloumn;j++){
                if(characters[i][j]!=null)
                    ans = ans+characters[i][j];
            }
        }
        return ans;

    }

    public ListNode reverseKGroup(ListNode head,int k){
        if(k==1||head==null)
            return head;

        ListNode tempHead = head;
        ListNode nextHead = null;
        ListNode tempTail = head;
        ListNode reverseHead = null;
        ListNode reverseTail = null;
        int flag = 1;
        while (true){

            if(flag==k)
            {
//                if(tempTail.next==null&&reverseHead==null)
//                    return head;

                if(tempTail.next!=null)
                    nextHead = tempTail.next;


                tempTail.next = null;
                if(reverseHead == null){
                    reverseHead = reverseList(tempHead);
                }

                if(reverseTail == null){
                    reverseTail = tempHead;
                }
                else
                {
                    reverseTail.next = reverseList(tempHead);
                    reverseTail = tempHead;
                }

                tempHead = nextHead;
                if(nextHead == null)
                    break;
                nextHead = null;
                tempTail = tempHead;

                flag = 1;

            }

            tempTail = tempTail.next;
            if(tempTail==null)
                break;
            flag++;
        }
        if(reverseTail==null||reverseHead==null)
            return head;
        reverseTail.next = tempHead;

        return reverseHead;
    }
    public ListNode reverseList(ListNode head){

        if(head.next==null)
            return head;
        ListNode returnHead = head;
        ListNode nextHead = head.next;
        ListNode tempHead = nextHead.next;

        while (tempHead!=null){
            nextHead.next = returnHead;
            returnHead = nextHead;
            nextHead  = tempHead;
            tempHead = tempHead.next;
        }
        nextHead.next = returnHead;
        head.next = null;
        return nextHead;

    }

    public ListNode mergeKLists(ListNode[] lists){
        int Length = lists.length;
        if(Length==0)
            return null;
        if(Length==1)
            return lists[0];

        ListNode temphead = lists[0];

        for(int i=1;i<Length;i++)
        {
            ListNode TempNode = new ListNode(-1);
            ListNode Temp = TempNode;
            while (lists[i]!=null&&temphead!=null)
            {
                if(lists[i].val<temphead.val)
                {
                    TempNode.next = lists[i];
                    lists[i] = lists[i].next;
                }
                else
                {
                    TempNode.next = temphead;
                    temphead = temphead.next;
                }
                TempNode = TempNode.next;

            }
            TempNode.next = (temphead==null)?lists[i]:temphead;
            temphead = Temp.next;
        }
        return temphead;
   }

    public ListNode mergeKListsBaseOnPriorityQueue(ListNode[] lists){
        int length = lists.length;
        if(length==1)
            return lists[0];
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val- o2.val;
            }
        });
        ListNode head = new ListNode(-1);
        ListNode tempHead = head;
        for(ListNode node:lists)
        {
            if(node!=null)
                queue.offer(node);
        }
        while (!queue.isEmpty())
        {
            ListNode node = queue.poll();
            if(node.next!=null)
                queue.offer(node.next);
            head.next = node;
            head = head.next;
        }

        return tempHead.next;
    }

    public int divide(int dividend,int divisor){
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        if(dividend==divisor)
            return 1;
        if(dividend==0)
            return 0;
        deque.addFirst(divisor);

        while (deque.peek()>=dividend)
        {
            deque.addFirst(deque.peek()+deque.peek());
        }
        int size = deque.size();
        if(deque.peek()==dividend)
            return 0;
        return 0;
    }

    public long quickExponentiation(long num,int n){
        long ans = 1l;
        while(n!=0)
        {
            if((n&1)==1)
            {
                ans = ans*num;
            }
            n = n>>1;
            num = num*num;
        }
        return ans;
    }

    public long quickMultiply(long num1,long num2){
        int index = 1;
        long sum = 0;
        while (num2!=0)
        {
            if((num2&1)==1)
            {
                sum = sum+index*num1;
            }
            index = index*2;
            num2 = num2>>1;
        }
        return sum;
    }

    public boolean isValidSudoKu(char[][] board){
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board){
        if(betterSolve(0,0,board)){
            for(int i = 0;i<9;i++){
                for(int j=0;j<9;j++){
                    System.out.print(board[i][j]+" ");
                }
                System.out.println();
            }
        }
    }
    private boolean solve(char[][] board){

        for(int i= 0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    for(int n=1;n<=9;n++)
                    {
                        board[i][j] = Integer.toString(n).charAt(0);
                        if(isValidSudoKu(board)){
                            if(solve(board)){
                                return true;
                            }
                        }
                    }

                    board[i][j]='.';
                    return false;
                }

            }
        }

        return true;

    }
    private boolean betterSolve(int row,int cloumn,char[][] board){
        if(row==8&&cloumn==9)
            return true;
        while (row!=8||cloumn!=9)
        {
            if(cloumn>8)
            {
                row++;
                cloumn = 0;
            }
            if(board[row][cloumn]=='.')
            {
                for(int i=1;i<=9;i++)
                {
                    board[row][cloumn] = Integer.toString(i).charAt(0);
                    if(isValidSudoKu(board)&&betterSolve(row,cloumn+1,board))
                        return true;
                }
                board[row][cloumn] = '.';
                return false;
            }
            cloumn++;
        }
        return true;
    }

    public boolean hasCycle(ListNode head){
        HashSet<ListNode> set = new HashSet<>();
        while (head != null)
        {
            if(!set.contains(head))
            {
                set.add(head);
                head = head.next;
            }
            else
                return true;
        }
        return false;
    }
    public boolean hasCycleBetter(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next!=null)
        {
            if(fast.next.next == null)
                return false;
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow)
                return true;
        }
        return false;
    }

    public ListNode detectCycle(ListNode head){
        HashSet<ListNode> set = new HashSet<>();
        while (head!=null)
        {
            if(!set.contains(head))
            {
                set.add(head);
            }
            else
                return head;
            head = head.next;
        }
        return null;
    }
    public ListNode detectCycleBetter(ListNode head){
        if(head == null)
            return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode temp = head;
        while (fast.next!=null)
        {
            if(fast.next==null)
                return null;
            else
                fast = fast.next.next;
            slow = slow.next;
            if(fast==slow)
            {
                System.out.println(fast.val);
                int flag  = 0;
                while (temp!=slow)
                {
                    temp = temp.next;
                    slow = slow.next;
                    flag++;
                }
                System.out.println(temp.val+" "+flag);
                return temp;
            }
        }
        return null;
    }

    public List<List<Integer>> subset(int[] nums){
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(new ArrayList<>(deque));
        findSubSet(nums,0,deque,lists);
        return lists;
    }
    private void findSubSet(int[] nums,int begin,ArrayDeque<Integer> collection,List<List<Integer>> lists){

        for(int i=begin;i<nums.length;i++)
        {
            collection.addLast(nums[i]);
//            System.out.println("添加： "+nums[i]);
            lists.add(new ArrayList<>(collection));
            findSubSet(nums,i+1,collection,lists);
//            System.out.println("删除： "+collection.getLast());
            collection.removeLast();
        }
    }

    public boolean exist(char[][] board,String word){
        boolean[][] isRoute = new boolean[board.length][board[0].length];
        for(int i = 0;i<board.length;i++)
        {
            for (int j = 0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0))
                {
                    isRoute[i][j] = true;
                    if(findChar(board,word,1,i,j,isRoute))
                    {
                        return true;
                    }
                    isRoute[i][j] = false;
                }

            }
        }
        return false;
    }
    private boolean findChar(char[][] board,String word,int index,int rows,int cloumn,boolean[][] isRoute){
        if(index==word.length())
            return true;
        if(rows-1>=0&&board[rows-1][cloumn]==word.charAt(index)&&!isRoute[rows-1][cloumn])
        {
            isRoute[rows-1][cloumn] = true;
            if(findChar(board,word,index+1,rows-1,cloumn,isRoute))
            {
                return true;
            }
            isRoute[rows-1][cloumn] = false;
        }
        if(rows+1<board.length&&board[rows+1][cloumn]==word.charAt(index)&&!isRoute[rows+1][cloumn])
        {
            isRoute[rows+1][cloumn] = true;
            if(findChar(board,word,index+1,rows+1,cloumn,isRoute))
            {
                return true;
            }
            isRoute[rows+1][cloumn] = false;
        }
        if(cloumn-1>=0&&board[rows][cloumn-1]==word.charAt(index)&&!isRoute[rows][cloumn-1])
        {
            isRoute[rows][cloumn-1] = true;
            if(findChar(board,word,index+1,rows,cloumn-1,isRoute))
            {
                return true;
            }
            isRoute[rows][cloumn-1] = false;
        }
        if(cloumn+1<board[0].length&&board[rows][cloumn+1]==word.charAt(index)&&!isRoute[rows][cloumn+1])
        {
            isRoute[rows][cloumn+1] = true;
            if(findChar(board,word,index+1,rows,cloumn+1,isRoute))
            {
                return true;
            }
            isRoute[rows][cloumn+1] = false;
        }
        return false;
    }

    public List<Integer> inorderTraversal(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        findTreeNode(list,root);
        return list;
    }
    private void findTreeNode(List<Integer> list,TreeNode root){
        if(root==null)
            return;
        findTreeNode(list,root.left);
        list.add(root.val);
        findTreeNode(list,root.right);
    }

    public int numTrees(int n){
        int[] val = new int[n+1];
        val[0] = 1;
        val[1] = 1;
        for(int i = 2;i<n+1;i++)
        {
            int sum = 0;
            for(int j=0;j<i;j++)
            {
                sum = val[j]*val[i-1-j]+sum;
            }
            val[i] = sum;
        }
        return val[n];
    }

    public boolean isValidBST(TreeNode root){
        return ValidBTS(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }
    public boolean ValidBTS(TreeNode root,long up,long lower){
        if(root==null)
            return true;
        if(root.val<=lower||root.val>=up)
            return false;
        return ValidBTS(root.right,up,root.val)&&ValidBTS(root.left,root.val,lower);
    }

    public boolean isSymmetric(TreeNode root){
        Queue<TreeNode> deque = new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while (!deque.isEmpty())
        {
            TreeNode left = deque.poll();
            TreeNode right = deque.poll();
            if(left==null&&right==null)
                continue;
            if((left==null&&right!=null)||(left!=null&&right==null))
                return false;
            if(left.val==right.val)
            {
                deque.add(left.left);
                deque.add(right.right);
                deque.add(left.right);
                deque.add(right.left);
            }
            else
                return false;
        }
        return true;
    }

    public List<List<Integer>> levelOrder(TreeNode root){
        Queue<TreeNode> queueOne = new LinkedList<>();
        Queue<TreeNode> queueTwo = new LinkedList<>();
        ArrayList<List<Integer>> lists = new ArrayList<>();
        if(root==null)
        {
            lists.add(new LinkedList<Integer>());
            return lists;
        }

        queueOne.add(root);
        boolean whichQueue = true;
        while (true)
        {
            if(whichQueue&&!queueOne.isEmpty())
            {
                List<Integer> list = new LinkedList<>();
                while (!queueOne.isEmpty())
                {
                    TreeNode node = queueOne.poll();
                    if(node!=null)
                    {
                        list.add(node.val);
                        if(node.right!=null||node.left!=null)
                        {
                            queueTwo.add(node.right);
                            queueTwo.add(node.left);
                        }
                    }

                }
                lists.add(list);
                whichQueue = false;
            }
            if(!whichQueue&&!queueTwo.isEmpty())
            {
                List<Integer> list = new LinkedList<>();
                while (!queueTwo.isEmpty())
                {
                    TreeNode node = queueTwo.poll();
                    if(node!=null)
                    {
                        list.add(node.val);
                        if(node.right!=null||node.left!=null)
                        {
                            queueOne.add(node.right);
                            queueOne.add(node.left);
                        }
                    }

                }
                lists.add(list);
                whichQueue = true;
            }
            if(queueTwo.isEmpty()&&queueOne.isEmpty())
                break;

        }
        return lists;
    }

    public int maxDepth(TreeNode root){
        return findMaxDepth(root,1);
    }
    private int findMaxDepth(TreeNode root,int depth){
        if(root==null)
            return depth-1;
        return Math.max(findMaxDepth(root.left,depth+1),findMaxDepth(root.right,depth+1));
    }

    public int singleNumber(int[] nums){
        if(nums.length==1)
            return nums[0];
        int temp = 0;
        for(int i = 0;i<nums.length;i++){
            temp = temp^nums[i];
        }
        return temp;
    }

    public int longestConsecutive(int[] nums){
        if(nums.length<=1)
            return nums.length;
        Arrays.sort(nums);
        int[] target = new int[nums.length];
        target[0] =1;
        int maxLength = 0;
        for(int i = 1;i<nums.length;i++){
            if(nums[i]-nums[i-1]==1){
                target[i] = target[i-1]+1;
            }
            else if(nums[i]-nums[i-1]==0)
            {
                target[i] =target[i-1];
            }
            else
                target[i] =1;
            if(target[i]>maxLength)
                maxLength = target[i];
        }

        return maxLength;
    }

    public int longestConsecutiveOffical(int[] nums){
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;

    }

    public int maxProfit(int[] prices){
        int [] profit = new int[prices.length];
        int maxProfit = 0;
        profit[0] = 0;
        for(int i=1;i<prices.length;i++){
            int tempProfit = prices[i]-prices[i-1]+profit[i-1];
            if(tempProfit>0){
                profit[i] = tempProfit;
                if(tempProfit>maxProfit)
                {
                    maxProfit = tempProfit;
                }
            }
            else
                profit[i] = 0;
        }
        return maxProfit;
    }








    



























}
